Many phases of the modern electronic design process are performed using computer aided design (CAD) tools or electronic design automation (EDA) systems. EDA tools are used to implement both printed circuit board (PCB) designs and integrated circuit (IC) designs. For example, an autorouter is a type of EDA tool that automatically determinations the path and location of wires and vias that route between different objects in an electronic design. For an IC design, the autorouter determines the layout and configuration of interconnect polygons and vias on the different metal layers of the IC. For a PCB design, the autorouter determines the configuration of wiring and vias that route between and among electronic objects on the different PCB layers. For an IC Package, the autorouter determines the path and location of wires and vias that route between the bumps (I/O connections) on the IC to the balls (pins) on the PCB. In a System-in-Package (SiP), the autorouter determines the path and location of wires and vias between multiple ICs and devices within the package to the exterior connections of the package.
Increasingly, the electronics industry is trending towards larger and/or more complex electronic designs and systems. Newer generations of IC design are continually escalating the number and concentration of objects that appear on the IC. For PCB and Sip designs, the industry trend is towards more complex designs having increased numbers of constraints. This increase in size and/or complexity dramatically increases the amount of design data for a given electronic design. As the quantity of data in modern electronic designs becomes larger over time, the execution time required to process EDA tools upon these electronic designs also becomes greater. For example, the amount of time needed to route an electronic design also increases as the design data becomes larger or more complex.
Many EDA tool vendors have the goal of improving their products to reduce processing time. For example, autorouters are often judged by their speed of execution. The goal of reducing EDA tool execution time is in sharp tension with the trend of modern electronic designs that are constantly increasing in complexity and/or size. This problem is exacerbated for all EDA tools by constantly improving manufacturing technologies.
To achieve faster tool processing results, it is often desirable to perform EDA processing using multi-processing approaches, e.g., concurrent or parallel processing. Examples of systems that support concurrent or parallel processing include multi-CPU/processor computers, multi-threaded systems, and distributed processing systems having multiple networked nodes.
Traditionally, many EDA tools such as autorouters did not support concurrency. The complexity of implementing autorouting algorithms made it impractical to consider making them concurrent. Recently, a few IC autorouters have begun to support concurrency. A commercially available example of an IC routing tool with concurrency is the Cadence Nanoroute product, available from Cadence Design Systems, Inc. of San Jose, Calif. USA. Most IC autorouters today consist of a global router and a detail router.
Due to the complexity of debugging and maintaining an autorouter, an extensive regression suite is generally needed or desired. If the autorouter is intended for multi-processing operation, then that regression suite must be able to test the multi-processing version of the product. However, such a regression suite would not be able to adequately test the autorouter unless the multi-processing autorouter can operate deterministically. Therefore, a deterministic, concurrent approach is needed to significantly improve performance of an autorouter, particularly for highly constrained designs.
The problem is that systems that exhibit chaotic behavior are notoriously difficult to debug and test. Such chaotic behavior includes a system where minor variations in early stages result in major variations in later stages. Of particular interest are autorouting algorithms, where deciding between two equally good choices for a single path results in dramatically different routing for the entire design. Similarly, concurrent systems are difficult to debug and test because the order of execution is unpredictable. When standard concurrent algorithms are applied to chaotic systems, the result is a product that is impossible to test or verify.
Embodiments of the present invention provide a method, system, and computer program product for implementing an EDA tool which provides deterministic multi-processing. A product is considered “deterministic” if its execution will always produce the same result under the same circumstances. The invention will therefore allow regression testing to verify proper operation of a product. Some embodiments of the invention provide a mechanism by which an EDA tool can be made thread-safe and executed in parallel and still be deterministic. In some embodiments, the invention is embodied as an autorouter that can be executed without negatively impacting quality using a deterministic costed-search approach. The inventive method and system may also be applied to other types of non-EDA systems and tools which employ multi-processing.
Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory, and are not intended to be limiting as to the scope of the invention.